package lc;

import org.junit.Test;

public class Ex440 {
    class Solution {
        public int findKthNumber(int n, int k) {
            int cur = 1, res = 1;
            while (cur < k) {
                int cnt = count(n, res);
                if (cur + cnt <= k) {
                    cur += cnt;
                    res++;
                } else {
                    cur++;
                    res *= 10;
                }
            }
            return res;
        }
    
        //p节点下（不包含p节点）所有节点的数量
        public int count(int n, int pre) {
            long cur = pre, next = cur + 1, sum = 0;
             while (cur <= n) {
                 sum += Math.min(next, n + 1) - cur;
                  cur *= 10;
                 next *= 10;
             }
             return (int)sum;
         }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        // System.out.println(s.count(100, 1)); 
        // System.out.println(s.findKthNumber(13, 2));    
        System.out.println(s.findKthNumber(681692778,351251360));   
    }
}
